 დინამიკური
პროგრამირება
   მარიამ გობრონიძე
ძირითადი თემები
•   ფრჩხილების ოპტიმალურად დასმა (Parenthesization).
•   მინიმალური მანძილი ორ სტრიქონს შორის (Edit Distance).
•   ზურგჩანთის ამოცანა (Knapsack problem).
Matrix Chain Multiplication – Optimal
Parenthesization
ამოცანა:
მოცემულია მასივი arr[], რომელიც წარმოადგენს მატრიცების
ჯაჭვს. ასეთი მატრიცის ზომა განსაზღვრულია ასე:
 i-ური მატრიცის განზომილება არის arr[i-1] x arr[i].
მიზანია, ვიპოვოთ ფრჩხილები (ანუ მატრიცების გაერთიანების
თანმიმდევრობა) ისე, რომ ყველა მატრიცის გადამრავლებისას
გამრავლების ოპერაციების რაოდენობა მინიმალური იყოს.
მაგალითი

Input: arr[] = [10, 20, 30]

Output: (AB)
ახსნა:
აქ მხოლოდ ორი მატრიცაა: A (10×20) და B (20×30).
მათ შორის ფრჩხილების დასმის მხოლოდ ერთი გზა არსებობს: (AB)
გამრავლების ღირებულება (საჭირო ოპერაციების რაოდენობა) იქნება:
10 × 20 × 30 = 6000
მაგალითი

Input: arr[] = [10, 20, 30, 40]
Output: ((AB)C)
ახსნა:
აქ სამი მატრიცაა:
 ●   A (10×20),

 ●   B (20×30),

 ●   C (30×40)
განვიხილოთ ფრჩხილების განლაგების სხვადასხვა ვარიანტები:
 1. ((AB)C) → ღირებულება:
    (10×20×30) + (10×30×40) = 6000 + 12000 = 18000

 2. (A(BC)) → ღირებულება:
    (20×30×40) + (10×20×40) = 24000 + 8000 = 32000
    მინიმალური ღირებულება მიიღწევა ((AB)C) ფორმით.
მაგალითი

Input: arr[] = [40, 20, 30, 10, 30]

Output: ((A(BC))D)
ახსნა:
მატრიცებია:

 ●   A: 40×20

 ●   B: 20×30

 ●   C: 30×10

 ●   D: 10×30
მაგალითი
ფრჩხილების განლაგების ვარიანტებია:
1. (((AB)C)D) → მნიშვნელობა: 48,000
2. ((A(BC))D) → მნიშვნელობა: 26,000
3. (A((BC)D)) → მნიშვნელობა: 36,000
4. ((AB)(CD)) → მნიშვნელობა: 69,000
5. (A(B(CD))) → მნიშვნელობა: 51,000

საუკეთესო შედეგი მიიღწევა ((A(BC))D) განლაგებით, რომლის
მნიშვნელობაა 26,000 ოპერაცია.
Using Recursion - O(2^n) Time and O(n)
Space
(i, j) ქვეამოცანისთვის მხოლოდ ოპტიმალური მნიშვნელობის
დაბრუნების ნაცვლად, ჩვენ ასევე ვაბრუნებთ მატრიცების
გამრავლების თანმიმდევრობას.
Using Top-Down DP (Memoization) -
O(n^3) Time and O(n^2) Space
დინამიკური პროგრამირება
(მემოიზაცია)
დავუშვათ, გვაქვს ოთხი მატრიცა: M1, M2, M3, M4.
თუ დავაკვირდებით რეკურსიულ მიდგომას, შეგვიძლია ავაგოთ რეკურსიის ხე.

თუ კარგად დავაკვირდებით, ვნახავთ, რომ ამოცანის ამოხსნა შესაძლებელია
დინამიკური პროგრამირებით.
1) ოპტიმალური ქვესტრუქტურა (Optimal Substructure):
ამ პრობლემას ვყოფთ მცირე ქვეჯგუფებად (ანუ მატრიცების მცირე ჯგუფებად) და
ვპოულობთ მათ გამრავლებისთვის საჭირო ოპერაციებს შორის მინიმუმს.
 ეს ნიშნავს, რომ პრობლემას აქვს ოპტიმალური ქვესტრუქტურის თვისება.

2) გადაფარვადი ქვეამოცანები (Overlapping Subproblems):
რეკურსიულ ხეში ვხედავთ, რომ ერთი და იგივე ქვეამოცანა გვხვდება მრავალჯერ,
რაც ნიშნავს, რომ პრობლემას გააჩნია გადაფარვადი ქვეამოცანები.
Using Bottom-Up DP(Tabulation) - O(n^3)
Time and O(n^2) Space
ეს მიდგომა მსგავსია წინა მეთოდის,
 თუმცა რეკურსიულად პრობლემის დაშლის ნაცვლად,
 პასუხს ვაგებთ იტერაციულად, ქვედა დონიდან ზევით (bottom-up) მეთოდით.

ამისათვის ვიყენებთ ორ განზომილებიან მასივს dp[][],
 ასე რომ dp[i][j] ინახავს წყვილს:

 ●   სტრინგს — რომელიც აღწერს მატრიცების გამრავლების თანმიმდევრობას (როგორ
     უნდა დავსვათ ფრჩხილები)

 ●   რიცხვს — რომელიც წარმოადგენს მინიმალურ ფასს მატრიცების
     გამრავლებისთვის შუალედში (i-დან j-მდე)
მინიმალური მანძილი ორ სტრიქონს შორის
(Edit Distance).
ამოცანა
მოცემულია ორი სტრიქონი: s1 და s2. ამოცანაა დავთავალოთ მინიმალური
საჭირო ოპერაციების რაოდენობა, რათა s1 გადავაქციოდ s2-ად.

დაშვებული ოპერაციები:

 ●   ჩასმა (Insert): ჩასვით ნებისმიერი სიმბოლო s1-ის ნებისმიერ პოზიციაზე (წინ
     ან შემდეგ)
 ●   წაშლა (Remove): წაშალეთ s1-ის ნებისმიერი სიმბოლო
 ●   შეცვლა (Replace): შეცვალეთ s1-ის ნებისმიერი სიმბოლო სხვა სიმბოლოთი

     შენიშვნა: ყველა ოპერაციის ღირებულება არის ერთი და იგივე.
  მაგალითები
Input: s1 = "geek", s2 = "gesek"
Output: 1
შეგვიძლია s1 გადავაქციოთ s2-ში, თუ 'e'-ებს შორის ჩავამატებთ სიმბოლოს 's'.
Input: s1 = "gfg", s2 = "gfg"
Output: 0
სტრიქონები ერთმანეთის იდენტურია
Input: s1 = "abcd", s2 = "bcfe"
Output: 3
შეგვიძლია s1 გადავაქციოთ s2-ად შემდეგი მოქმედებებით:

 ●    წავშალოთ 'a',
 ●    'd' შევცვალოთ 'f'-ით,
 ●    ბოლოში ჩავამატოთ 'e'.
Using Recursion-O(3^(m+n)) time and
space O(m*n)
იდეა შემდეგია — ორივე სტრიქონის სიმბოლოებს ვამუშავებთ თანმიმდევრობით, რომელიმე
ბოლოდან. დავუშვათ, ვიწყებთ სტრიქონების მარჯვენა ბოლოდან.

ამ შემთხვევაში, ყოველ წყვილზე ორი შესაძლო ვარიანტი არსებობს:

 1. თუ სიმბოლოები ემთხვევა — უბრალოდ რეკურსიულად გადავდივართ სტრიქონების
    დარჩენილ ნაწილზე, რადგან ამ ეტაპზე სხვა ოპერაციის ჩატარება საჭირო არ არის.
 2. თუ სიმბოლოები არ ემთხვევა —
    ვცდით სამივე ოპერაციას:
 ● ჩასმა (Insert)
 ● შეცვლა (Replace)
 ● წაშლა (Remove)

თითოეული ოპერაციის შემდეგ, რეკურსიულად ვაგრძელებთ მუშაობას დარჩენილ
სტრიქონებზე და ბოლოს ვირჩევთ მინიმალურ შედეგს ამ სამიდან და ვუმატებთ 1-ს,
რაც აღნიშნავს შესრულებულ ოპერაციას.
რეკურსიული ხე, როცა ბოლო სიმბოლოები არასოდეს ემთხვევა
როდესაც სტრიქონების ბოლო სიმბოლოები ემთხვევა —
ვიძახებთ: editDistance(m-1, n-1) რეკურსიულად რაც ნიშნავს, რომ
პასუხს ვპოულობთ დარჩენილი სტრიქონისთვის.
როდესაც სტრიქონების ბოლო სიმბოლოები არ ემთხვევა —
ვაკეთებთ სამ რეკურსიულ გამოძახებას:

1. ჩასმა – ჩავამატოთ s2[n-1] სიმბოლო s1-ის ბოლოს:
    editDistance(m, n-1)
2. შეცვლა – s1[m-1] შევცვალოთ s2[n-1]-ით:
    editDistance(m-1, n-1)
3. წაშლა – წავშალოთ s1[m-1]:
    editDistance(m-1, n)
რეკურსია
 1. შემთხვევა 1: როცა ბოლო სიმბოლოები ემთხვევა: editDistance(s1, s2,
    m, n) = editDistance(s1, s2, m-1, n-1)
 2. შემთხვევა 2: როცა ბოლო სიმბოლოები განსხვავებულია:
editDistance(s1, s2, m, n) = 1 + Minimum{ editDistance(s1, s2 ,m,n-1), editDistance(s1, s2
,m-1, n), editDistance(s1, s2 , m-1, n-1)}
საბაზისო შემთხვევა

შემთხვევა 1: თუ s1 ცარიელია, ანუ m = 0
     ვაბრუნებთ n-ს, რადგან საჭიროა n ჩასმა, რომ ცარიელი სტრიქონი
ვაქციოთ s2-დ (სიგრძე n).

შემთხვევა 2: თუ s2 ცარიელია, ანუ n = 0
     ვაბრუნებთ m-ს, რადგან საჭიროა m სიმბოლოს წაშლა, რომ s1 (სიგრძე m)
ვაქციოთ ცარიელ სტრიქონად.
Using Top-Down DP (Memoization) -
O(m*n) time and O(m*n) space
ზემოთ აღწერილ რეკურსიულ მიდგომაში არსებობს მრავალი დამთხვევადი
ქვეამოცანა:

მაგალითად:

 ●   editDist(m-1, n-1) გამოიძახება სამჯერ,
 ●   editDist(m-1, n-2) გამოიძახება ორჯერ,
 ●   editDist(m-2, n-1) გამოიძახება ორჯერ,
     და ასე შემდეგ...

ამიტომ, შეგვიძლია გამოვიყენოთ მემოიზაცია, რათა თითოეული ქვეამოცანის
შედეგი ერთხელ დავიმახსოვროთ და თავიდან ავირიდოთ ერთიდაიგივე
გამოთვლის მრავალჯერადი შესრულება.

ქვემოთ მოცემულია ვიზუალიზაცია იმისა, თუ როგორ მეორდება ქვეამოცანები
რეკურსიის დროს.
Using Bottom-Up DP (Tabulation)-O(m*n)
time and O(m*n) space
 1. ცხრილის განზომილებების შერჩევა: ქვეამოცანების მდგომარეობა
    დამოკიდებულია შეყვანილ პარამეტრებ m და n-ზე, რადგან
    თითოეული რეკურსიული გამოძახების შემდეგ მინიმუმ ერთი
    მათგანი მცირდება.
ამიტომ ჩვენ უნდა შევქმნათ 2D ცხრილი dp[][] ქვეამოცანების
პასუხების შესანახად.
2. ცხრილის სწორი ზომის არჩევა: პარამეტრების დიაპაზონი 0-დან
m-მდე და 0-დან n-მდე იცვლება. ამიტომაც შევქმნით (m + 1) * (n + 1)
განზომილებიან ცხრილს.
3. ცხრილის შევსება:

შედგება ორი ეტაპისგან, ცხრილის ინიცირება და მცირე
ქვეამოცანების შედეგების პოვნა:
ცხრილის ინიცირება: ამონახსნების პოვნამდე, ჩვენ უნდა შევქმნათ
ცხრილი ცნობილი მნიშვნელობებით, ანუ საბაზისო შემთხვევით. აქ
m = 0 და n = 0 არის საბაზისო შემთხვევები, ასე რომ ჩვენ
ინიციალიზაციას ვაკეთებთ პირველი სვეტის dp[i][0]-ს i-ით და
პირველი სტრიქონის dp[0][j]-ს j-ით.
მცირე ქვეამოცანების შედეგების პოვნა: ჩვენ შეგვიძლია ადვილად
განვსაზღვროთ იტერაციული სტრუქტურა ზემოთ მოყვანილი
რეკურსიული ამოხსნის მიხედვით.
თუ (s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1]; თუ (s1[i - 1] ! = s2[j - 1])
dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]);
4. საბოლოო შედეგის დაბრუნება: ცხრილის იტერაციული შევსების
შემდეგ, ჩვენი საბოლოო გადაწყვეტილება ინახება 2D ცხრილის
ქვედა მარჯვენა კუთხეში, ანუ ჩვენ ვბრუნდებით dp [m] [n].
ზურგჩანთის ამოცანა (Knapsack problem)

მოცემულია n ნივთი, სადაც თითოეულ ნივთს აქვს გარკვეული წონა
და დაკავშირებულია გარკვეულ მოგებასთან, ასევე მოცემულია ჩანთა
W ტევადობით, [ანუ, ჩანთას შეუძლია შეინახოს მაქსიმუმ W წონა
მასში]. ამოცანაა, რომ ჩანთაში ისეთი ნივთები ჩავდოთ, რომ მათთან
დაკავშირებული მოგების ჯამი მაქსიმალური იყოს.
შენიშვნა
ჩანთში ნივთი ან მთლიანად უნდა ჩავდოთ ან არ ჩავდოთ
[შეუძლებელია ნივთის ნაწილის ჩადება ჩანთაში].
მაგალითი
Input: W = 4, მოგება [] = [1, 2, 3], წონა [] = [4, 5, 1]
Output: 3
არსებობს ორი ნივთი, რომელთა წონა 4-ზე ნაკლები ან ტოლია. თუ
შევარჩევთ ნივთს, რომლის წონაა 4, შესაძლო მოგება იქნება 1. თუ
შევარჩევთ ნივთს, რომლის წონაა 1, შესაძლო მოგება იქნება 3.
მაქსიმალური შესაძლო მოგება არის 3.


Input: W = 3, მოგება [] = [1, 2, 3], წონა [] = [4, 5, 6]
Output: 0
Using Recursion O(2^n) Time and O(n)
Space
იდეა
მარტივი გამოსავალია განვიხილოთ ნივთების ყველა ქვეჯგუფი და
თითოეული ქვეჯგუფისთვის გამოვთვალოთ მათი ჯამური წონა და
ჯამური ღირებულება. განვიხილოთ მხოლოდ ის ქვეჯგუფები,
რომელთა საერთო წონა ნაკლებია მოცემულ W-ზე. ასეთი
ქვეჯგუფებიდან ავირჩიოთ ის, რომელსაც მაქსიმალური ღირებულება
აქვს.
როგორ დავთალოთ ‘n’ რაოდენობის ნივთიდან მიღებული მაქსიმალური
ღირებულება
 1. შემთხვევა 1 (ვირჩევთ მე-n-ე ნივთს):
    მე-n-ე ნივთის ღირებულება + დარჩენილი (n-1) ნივთიდან და
    დარჩენილი წონისგან მიღებული მაქსიმალური ღირებულება, ანუ W
    – მე- n-ე ნივთის წონა
 1. შემთხვევა 2 (არ ვირჩევთ მე-n-ე ნივთს):
     (n-1) ნივთიდან მიღებული მაქსიმალური ღირებულება სრული
    წონისთვის W

თუ მე-n-ე ნივთის წონა მეტია W-ზე, მაშინ მე-n-ე ნივთის არჩევა
შეუძლებელია და მხოლოდ შემთხვევა 2 განიხილება.
Using Top-Down DP (Memoization)- O(n x
W) Time and Space
იდეა

იმის გამო, რომ ერთიდაიგივე ქვეამოცანა განმეორებით ჩნდება, შეგვიძლია
გამოვიყენოთ შემდეგი იდეა პრობლემის ეფექტურად გადასაჭრელად:

როდესაც პირველად ვხვდებით ამოცანას, შეგვიძლია იგი გადავჭრათ ისე, რომ
შევქმნათ ორგანზომილებიანი მასივი (ცხრილი), რომელიც შეინახავს კონკრეტულ
მდგომარეობას — (n, w), სადაც n არის ნივთების რაოდენობა და w — დარჩენილი
წონა.

ამის შემდეგ, თუ ისევ შევხვდებით იმავე მდგომარეობას (n, w), განმეორებითი
გამოთვლის ნაცვლად, შეგვიძლია ცხრილიდან პირდაპირ დავაბრუნოთ ამ
მდგომარეობისთვის უკვე გამოთვლილი შედეგი, რაც მოხდება მუდმივ დროში.
Using Bottom-Up DP (Tabulation) - O(n x
W) Time and Space
იდეა
რეკურსიულ ამოხსნაში ორი პარამეტრი იცვლება — ეს პარამეტრები მერყეობს 0-
დან n-მდე და 0-დან W-მდე. შესაბამისად, ვქმნით ორგანზომილებიან dp[][]
მასივს ზომით (n+1) x (W+1), სადაც dp[i][j] ინახავს იმ მაქსიმალურ
ღირებულებას, რომელსაც მივიღებთ i ნივთის გამოყენებით მაშინ, როდესაც
ზურგჩანთის ტევადობა არის j.
ჯერ ვავსებთ იმ უჯრებს, რომლებიც ცხადად ცნობილია — როდესაც i (ნივთების
რაოდენობა) ან j (ტევადობა) არის 0.

შემდეგ ვავსებთ დანარჩენ უჯრებს რეკურსიული ფორმულის მიხედვით.
თითოეული ნივთისთვის i და ტევადობისთვის j ვწყვეტთ, ავიღოთ თუ არა ეს
ნივთი.

 ●   თუ ნივთს არ ვიღებთ:
     dp[i][j] რჩება იგივე, რაც წინა ნივთისთვის იყო, ანუ dp[i - 1][j]

 ●   თუ ნივთს ვიღებთ:
     dp[i][j] განახლდება შემდეგნაირად: val[i] + dp[i - 1][j -
     wt[i]]
გმადლობთ ყურადღებისთვის!
